package dfs

var (
	gridMarkArr [][]byte
	posMarkArr  [][]int
	gridLenX    int
	gridLenY    int
)

func min(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

func dfsMarkIsland(x, y int, isIsland bool, currentMarkNum int) {
	if !isIsland {
		if gridMarkArr[x][y] == 1 {
			// 边界条件：当前位置标记数为0，表示从来没遍历过，直接标记为上一个位置的标记值
			if posMarkArr[x][y] == 0 {
				posMarkArr[x][y] = currentMarkNum + 1
			} else {
				// 注意从0 调到1 是以更大为准，和下面从岛跳到岛逻辑相反，因为 岛屿可能存在“伪大”的可能，但是从海到岛不可能
				posMarkArr[x][y] = max(currentMarkNum+1, posMarkArr[x][y])
			}
		} else {
			posMarkArr[x][y] = currentMarkNum
		}
	} else {
		if gridMarkArr[x][y] == 1 {
			if posMarkArr[x][y] == 0 {
				posMarkArr[x][y] = currentMarkNum
			} else {
				posMarkArr[x][y] = min(currentMarkNum, posMarkArr[x][y])
			}
		} else {
			posMarkArr[x][y] = currentMarkNum
		}
	}
	isIsland = gridMarkArr[x][y] == 1
	// 只会往前遍历
	if x < gridLenX-1 {
		dfsMarkIsland(x+1, y, gridMarkArr[x][y] == 1, posMarkArr[x][y])
	}
	if y < gridLenY-1 {
		dfsMarkIsland(x, y+1, gridMarkArr[x][y] == 1, posMarkArr[x][y])
	}
}

// https://leetcode-cn.com/problems/number-of-islands/
func NumIslands(grid [][]byte) int {
	gridLenX = len(grid)
	gridLenY = len(grid[0])
	posMarkArr = make([][]int, gridLenX)
	for index := 0; index < gridLenX; index++ {
		posMarkArr[index] = make([]int, gridLenY)
	}
	gridMarkArr = grid

	// dfs 遍历每一个位置的状态
	if gridMarkArr[0][0] == 1 {
		posMarkArr[0][0] = 1
	}
	dfsMarkIsland(0, 0, gridMarkArr[0][0] == 1, posMarkArr[0][0])

	// 遍历所有标记位，输出最大的下标，就是岛屿的数量
	maxIslandMark := 0
	for _, currentSlice := range posMarkArr {
		for _, currentMark := range currentSlice {
			if maxIslandMark < currentMark {
				maxIslandMark = currentMark
			}
		}
	}
	//return maxIslandMark
	return posMarkArr[gridLenX-1][gridLenY-1]
}
